﻿using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_155 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 18;

            var dct = new Dictionary<long, HashSet<SmallRational>>
                          {
                              {1, new HashSet<SmallRational>(){1}},
                              {2, new HashSet<SmallRational>(){2, new SmallRational(1,2)}}
                          };
            var index = 2;
            long cnt = 3;
            while (true)
            {
                index++;
                if (index > max)
                    break;
                var tmp = new HashSet<SmallRational>();
                for (int i = index-1; i >= index / 2; i-- )
                {
                    foreach (var rational in dct[i])
                    {
                        foreach (var rational2 in dct[index-i])
                        {
                            var q = rational + rational2;
                            if (!tmp.Contains(q))
                            {
                                var ex = false;
                                foreach (var pair in dct)
                                {
                                    if (pair.Value.Contains(q))
                                    {
                                        ex = true;
                                        break;
                                    }
                                }
                                if (!ex)
                                    tmp.Add(q);
                            }
                            q = 1/(1/rational + 1/rational2);
                            if (!tmp.Contains(q))
                            {
                                var ex = false;
                                foreach (var pair in dct)
                                {
                                    if (pair.Value.Contains(q))
                                    {
                                        ex = true;
                                        break;
                                    }
                                }
                                if (!ex)
                                    tmp.Add(q);
                            }
                        }
                    }
                }
                dct.Add(index, new HashSet<SmallRational>(tmp));
                cnt += tmp.Count;
            }
            return cnt;
        }

        public override string Problem
        {
            get
            {
                return @"An electric circuit uses exclusively identical capacitors of the same value C. 
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to n=3 capacitors of 60 F each, we can obtain the following 7 distinct total capacitance values:


If we denote by D(n) the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors and the simple procedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...

Find D(18).

Reminder : When connecting capacitors C1, C2 etc in parallel, the total capacitance is CT = C1 + C2 +..., 
whereas when connecting them in series, the overall capacitance is given by: ";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 3857447;
            }
        }
    }
}
